Bareiss algorithm

In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be exact (there is no remainder). The method can also be used to compute the determinant of matrices with (approximated) real entries, avoiding the introduction any round-off errors beyond those already present in the input.

For an n × n matrix of maximum (absolute) value 2^L for each entry, the Bareiss algorithm runs in O(n³) elementary operations with an O(n ⁿ 2^nL) bound on the absolute value of intermediate values needed.

Calculating the determinant

To compute the determinant using the bareiss algorithm you must find the total number of elements in each row and multiply them by the total number of elements in each column.

References

• Bareiss, Erwin (1968), "Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination", Mathematics of computation 22 (102): 565–578, http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf .

External links

• Yap, Chee, "Linear Systems", Fundamental Problems of Algorithmic Algebra, http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz